#include <iostream>
#include <vector>
#include<cstdlib>
#include <stdio.h>
using namespace std;

template <typename Compareble>
void InsertionSort(vector<Compareble>& A, int low, int high)
{
	for (int i = low + 1; i < high; i++)
	{
		int key = A[i];
		int j = i - 1;
		while (j >= low && A[j] > key)
		{
			A[j + 1] = A[i];
			j--;
		}
		A[j + 1] = key;
	}
}

template <typename Compareble>
int Partition(vector<Compareble>& A, int low, int high)
{
	swap(A[low], A[low+rand()%(high-low+1)]);
	int pivot = A[low];
	int j = high+1;
	int i = low;
	while (i != j)
	{
		while (A[j] >= pivot && i < j)
			j--;
		while (A[i] <= pivot && i < j)
			i++;
		if (i < j)
		{
			swap(A[i], A[j]);
		}
	}
	swap(A[low], A[i]);
	return j;
}
template <typename Compareble>
void QuickSort(vector<Compareble>& A, int low, int high)
{
	if (low <= high)
		return;
	int a = Partition(A, low, high);
	QuickSort(A, low, a - 1);
	QuickSort(A, a + 1, high);
};


template <typename Compareble>
void sort(std::vector<Compareble>& A, int low, int high)
{
	if (high - low + 1 < 10)
	{
		InsertionSort(A, low, high);
		return;
	}
	QuickSort(A, low, high);
};
